package org.aplombh.java.awcing.basic.dp.linearDP;

import java.io.*;

/**
 * 给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
 * <p>
 * 输入格式
 * 第一行包含两个整数 N 和 M。
 * <p>
 * 第二行包含一个长度为 N 的字符串，表示字符串 A。
 * <p>
 * 第三行包含一个长度为 M 的字符串，表示字符串 B。
 * <p>
 * 字符串均由小写字母构成。
 * <p>
 * 输出格式
 * 输出一个整数，表示最大长度。
 * <p>
 * 数据范围
 * 1≤N,M≤1000
 * 输入样例：
 * 4 5
 * acbd
 * abedc
 * 输出样例：
 * 3
 */
public class LongestCommonSubsequence_897 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int n = Integer.parseInt(s.split(" ")[0]);
        int m = Integer.parseInt(s.split(" ")[1]);
        String a = reader.readLine();
        String b = reader.readLine();
        LongestCommonSubsequence lcs = new LongestCommonSubsequence();
        System.out.println(lcs.solve(a, b));

    }
}

class LongestCommonSubsequence {
    public static final int N = 1010;
    int[][] f = new int[N][N];
    int n, m;
    int[][] path = new int[N][N];

    public int solve(String a, String b) {
        char[] x = a.toCharArray();
        char[] y = b.toCharArray();
        n = a.length();
        m = b.length();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                if (f[i - 1][j] > f[i][j - 1]) {
                    f[i][j] = f[i - 1][j];
                    path[i][j] = 1;
                } else {
                    f[i][j] = f[i][j - 1];
                    path[i][j] = 2;
                }
                if (x[i - 1] == y[j - 1] && f[i - 1][j - 1] + 1 > f[i][j]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    path[i][j] = 3;
                }

            }
        }
        path(a, b);
        return f[n][m];
    }

    public void path(String a, String b) {
        StringBuilder str = new StringBuilder();
        for (int i = n, j = m; i > 0; ) {
            if (path[i][j] == 1) {
                i--;
            } else if (path[i][j] == 2) {
                j--;
            } else {
                str.append(a.charAt(i - 1));
                i--;
                j--;
            }
        }
        str.reverse();
        System.out.println(str);
    }
}